package Classic150;

import Tree.TreeNode;

public class 完全二叉树的节点个数 {
    /*
        利用完全二叉树的性质
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftLen = 1, rightLen = 1;
        for (TreeNode left = root.left; left != null; left = left.left) leftLen++;
        for (TreeNode right = root.right; right != null; right = right.right) rightLen++;
        if (leftLen == rightLen) return (int) Math.pow(2, leftLen) - 1;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
